class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //canBreak表示s中元素是否可分割，在两个true之间的字符串存在于字典中（[true,true)]）
        boolean[] canBreak = new boolean[s.length() + 1];
        canBreak[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = i - 1; j >= 0; j--){
                if(canBreak[j] && wordDict.contains(s.substring(j,i))){
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }
}